1. Field of the Invention
This invention relates to data processing systems and more particularly to a hierarchical memory employing a high speed backing store and several smaller lower speed buffer stores.
2. Prior Art
An article by C. J. Conti entitled "Concepts For Buffer Storage" published in the IEEE Computer Group News, March, 1969, describes a hierarchical memory in which a large slow speed three dimensional core storage operates in conjunction with a relatively small high speed buffer storage (or cache) manufactured using integrated circuit technology. By using the buffer/backing store arrangement, the central processing unit (CPU) is able to access data at a high rate from the high speed buffer which is matched more closely to the machine cycle of the CPU. When the CPU provides the address of desired information to the hierarchical memory, a control circuit determines whether or not the addressed data has been moved from the backing store to the buffer store. If the data is located in the buffer store, high speed access is possible from the buffer store to the CPU. If the data is not in the buffer store, controls move the data from the backing store to the high speed buffer and access is possible. A use algorithm is provided to insure that the most frequently used data is stored in the high speed buffer and the data most likely not to be used frequently is stored in the larger backing store. If the use algorithm is efficient, most accesses will be to the higher speed buffer store. This should result in a combined system having effective speeds approaching that of the fastest memory at a cost approaching that of the slowest and least expensive memory. Examples of hierarchical memories may be found in U.S. Pat. No. 3,588,829, Ser. No. 776,858, filed Nov. 14, 1968 which discloses separate and distinct memory modules and in U.S. Pat. No. 3,740,723 based upon Patent Application Ser. No. 101,658, filed Dec. 28, 1970 wherein an integrated hierarchical memory device is disclosed.
In the prior art, buffer/backing storage apparatus are transparent to the user and the buffer operation is under fixed hardware control. When a CPU initiates a fetch operation, the main storage address is presented to the memory hierarchy. Controls access the address search mechanism of the high speed buffer to determine if the requested address currently resides in the high speed buffer. If the requested information is in the buffer, it is immediately made available to the CPU. If the requested information is not currently in the buffer, a fetch operation is initiated to the main storage backing store. The buffer location to receive the information from main storage is determined by replacement logic which, in accordance with some predetermined algorithm determines which address in the buffer store is to returned to the backing store and replaced with the new data unit. When the fetch is initiated at the main storage, the exact word requested is first accessed and sent directly to the CPU and the buffer followed by the remaining words in the same transferrable data unit as determined by the particular block size of the system.
There are currently three methods in the prior art for handling store operations. The "store through" method is used on most existing systems and the data is always stored immediately in the main storage and the buffer address mechanism is checked to determine if the address block is currently in the buffer. In the block is in the buffer, the data is also stored in the buffer. However, on some systems, the buffer block is made invalid and any subsequent fetches to the same block require accessing the main storage to fetch the data to the buffer.
A second method is the "store wherever". In this method, the buffer address mechanism is checked to determine if the address block is currently in the buffer. If the block is in the buffer, the data is stored directly into the buffer without further action. If the block is not in the buffer, the data is stored in the main storage.
The third method "store in buffer" brings the block from main storage and then stores the new data into the block and the buffer.
In most existing systems, input/output data transfers access the main storage directly. Input operations are similar to those described for the store through operations from the CPU. That is, the block is stored into if it is currently in the buffer. It is possible, however, to utilize the scheme wherein the block is invalidated or deleted from the buffer when the addressed memory area in main storage is stored into from the I/O.
The prior art systems have some serious drawbacks. There is interference between CPU and input/output channels accessing the same main storage. That is, when a CPU accesses data in a common buffer, its data accessing has an effect on the use algorithm and therefore is a factor in determining what data is brought from the backing store into the buffer. In systems where the channels operate through the same buffer as the CPU, the channels interfere with the use logic and also have an effect on what data is stored in the buffer. Therefore, the CPU's and the channels interfere with each other and each is a factor in determining what data is stored in the buffer.
It is therefore an object of this invention to provide a hierarchical memory system in which CPU's and channels operate in an overlapped manner without interference.
It is also an object of this invention to provide a hierarchical memory system in which buffers are dedicated to certain data handling functions to provide a means for performing said functions without interference.
The above objects are accomplished in accordance with the present invention by providing separate independently operable high speed buffers dedicated to separate partitionable data handling tasks and matched in speed and/or page (data-unit) size to the tasks. The dedicated buffers all operate in conjunction with a large low speed main storage. Any user first tries to access its own dedicated buffer. If the required data unit is found in the user's dedicated buffer, the user accesses the information updating the use code for each use. If the required data unit is not in the dedicated buffer, a simultaneous search for the data is started on all other buffers. If the required data unit is found in some other buffer, the user accesses the data from that buffer but the use code for the buffer is not changed. The data unit in main storage is ignored, and the user's dedicated buffer is not altered.
If the desired data unit is not found in any of the buffers, the address is accessed in main storage and the least recently used data unit from the user's dedicated buffer is returned to its appropriate location in main storage. The requested data unit is transferred from main storage to the user's dedicated buffer and is stored with its address in the location vacated by the least recently used data unit.
This system has the advantage that data handling tasks such as problem programs, supervisor programs, and I/O programs can be performed independently and in an overlapper manner without interference with each other.